/*  geometry.h
 * Copyright (C) 2010, Francisco Claude & Patrick Nicholson, all rights reserved.
 *
 * Francisco Claude & Patrick Nicholson <(fclaude|p3nichol)@cs.uwaterloo.ca>
 *
 *   This program is free software: you can redistribute it and/or modify
 *   it under the terms of the GNU General Public License as published by
 *   the Free Software Foundation, either version 3 of the License, or
 *   (at your option) any later version.
 *
 *   This program is distributed in the hope that it will be useful,
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *   GNU General Public License for more details.
 *
 *   You should have received a copy of the GNU General Public License
 *   along with this program.  If not, see <http://www.gnu.org/licenses/>.
 *
 */

#include<iostream>
#include<fstream>
#include<sstream>
#include<algorithm>
#include<vector>
#include<map>
#include<list>
#include<queue>
#include<stack>

using namespace std;

#include "point.h"

#ifndef GEOMETRY_H
#define GEOMETRY_H

// Code from "Computational Geometry in C", second edition, by Joseph O'Rourke
inline double area2(const Point * p1, const Point * p2, const Point * p3) {
  return (p2->getX()-p1->getX())*(p3->getY()-p1->getY()) - (p3->getX()-p1->getX())*(p2->getY()-p1->getY());
}

// Code from "Computational Geometry in C", second edition, by Joseph O'Rourke
inline bool left(const Point * p1, const Point * p2, const Point * p3) {
  return area2(p1,p2,p3)>0;
}

// Code from "Computational Geometry in C", second edition, by Joseph O'Rourke
inline bool collinear(const Point * p1, const Point * p2, const Point * p3) {
  double a = area2(p1,p2,p3);
  if(a<0) a*=-1;
  return a<=1e-16;
}

// Code from "Computational Geometry in C", second edition, by Joseph O'Rourke
inline bool cross(const Point * p1, const Point * p2, const Point * p3, const Point * p4) {
  if(collinear(p1,p2,p3) || collinear(p1,p2,p4) || collinear(p3,p4,p1) || collinear(p3,p4,p2)) {
    return false;
  }
  //return (left(p1,p2,p3)^left(p1,p2,p4)) && (left(p3,p4,p1)^left(p3,p4,p2));
  return area2(p1,p2,p3)*area2(p1,p2,p4) < 0 && area2(p3,p4,p1)*area2(p3,p4,p2) < 0;
}

// Code from "Computational Geometry in C", second edition, by Joseph O'Rourke
inline bool between(const Point * p1, const Point * p2, const Point * p3) {
  if(!collinear(p1,p2,p3)) return false;
  if(p1->getX() != p2->getX()) {
    return (p1->getX() <= p3->getX() && p3->getX() <= p2->getX()) ||
            (p1->getX() >= p3->getX() && p3->getX() >= p2->getX());
  } else {
    return (p1->getY() <= p3->getY() && p3->getY() <= p2->getY()) ||
            (p1->getY() >= p3->getY() && p3->getY() >= p2->getY());
  }
}

/** Checks whether p is in the rectangle defined by p1 and p2 */
inline bool inside(const Point & p, const Point & p1, const Point & p2) {
  if(!(p.getX() >= p1.getX() && p.getY() >= p1.getY() && p.getX() <= p2.getX() && p.getY() <= p2.getY()))
    return false;
  return true;
}

/** Checks is p2 is to the right and down from p1 */
inline bool compatibleDes(const Point & p1, const Point & p2) {
  return p1.getX() <= p2.getX() && p1.getY() >= p2.getY();
}

/** Checks is p2 is to the right and up from p1 */
inline bool compatibleAsc(const Point & p1, const Point & p2) {
  return p1.getX() <= p2.getX() && p1.getY() <= p2.getY();
}

#endif

